/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年05月27日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if(size == 0 ){
            return 0;
        }

        vector<vector<int>> dp(size, vector<int>(3, 0));
        dp[0][0] = 0; //不持股
        dp[0][1] = -1 * prices[0]; //持股
        dp[0][2] = 0; //卖出
        for(int i = 1; i < size; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
            dp[i][2] = dp[i-1][1] + prices[i];
        }

        return max(dp[size-1][2], dp[size-1][0]);
    }
};